class Solution
{
public:
    vector<int> postorderTraversal(TreeNode *root)
    {
        vector<int> res;
        if (root == NULL)
            return res;

        stack<TreeNode *> s;
        TreeNode *cur;        //当前结点
        TreeNode *pre = NULL; //前一次访问的结点

        s.push(root);
        while (!s.empty())
        {
            cur = s.top();

            if ((cur->left == NULL && cur->right == NULL) || (pre != NULL && (pre == cur->left || pre == cur->right)))
            {
                //如果当前结点没有孩子结点或者孩子节点都已被访问过
                res.push_back(cur->val);
                s.pop();
                pre = cur;
            }

            else
            {
                if (cur->right != NULL)
                    s.push(cur->right);

                if (cur->left != NULL)
                    s.push(cur->left);
            }
        }

        return res;
    }
};